package com.hanxiaozhang.sort;

import com.hanxiaozhang.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈插入排序〉
 *
 * @author hanxinghua
 * @create 2021/9/2
 * @since 1.0.0
 */
public class InsertSort {


    /**
     * 插入排序算法思想：插入排序在排序过程中是局部有序，随着插入项的增多，有序部分的项的位置会发生改变。
     * 首轮，选择第二项作为插入项，然后取出这一项放在一个变量中，与前一项比较，而且小，则前一项后移到第二项的位置，
     * 然后第二项也就是插入项放在前一项的位置。
     * 第二轮，选择第三项作为插入项然后取出和前一项也就是第二项比较如果小，第二项后移到插入项，
     * 然后插入相在和第一项比较如果小，则第一项后移到第二项，插入项放在第一项。
     * 以此类推。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {9, 3, 21, 1, 66};
        System.out.println(Arrays.toString(insertSort1(arr)));
    }

    /**
     * 从后往前比
     *
     * @param arr
     * @return
     */
    private static int[] insertSort(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    AlgorithmUtil.swap_2(arr, j, j - 1);
                }
            }
        }
        return arr;
    }

    /**
     * 从前往后比
     *
     * @param arr
     * @return
     */
    private static int[] insertSort1(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) {
                    AlgorithmUtil.swap_1(arr, j, i);
                }
            }
        }
        return arr;
    }
}
